package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-11
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 */
public class leetcode316 {

    public String removeDuplicateLetters(String s) {

        char[] letters = s.toCharArray();
        int lastIndex[] = new int[26];  //每个字母最后出现的下标
        boolean isVisited[] = new boolean[26]; //每个字母是否已经存在栈中

        for (int i = 0; i < letters.length; i++) {
            lastIndex[letters[i]-'a'] = i;
        }

        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < letters.length; i++) {
            if (isVisited[letters[i]-'a']) continue;

            //注意此处用while，例如"bcabc"，在for进行到a时，while循环会把栈中的bc都移除
            while (!stack.isEmpty() && stack.peekLast() > letters[i] && lastIndex[stack.peekLast()-'a']>i){
                Character top = stack.removeLast();
                isVisited[top-'a'] = false;
            }

            stack.add(letters[i]);
            isVisited[letters[i]-'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}
